As network equipment and mobile terminals have become popular, a technology for controlling a device that can be controlled via a network from a mobile terminal has attracted attention. As an example, electronic boards that are capable of controlling the operation of switching on and off a device such as a bulb via a network, projectors that can be controlled via a network and the like have become widely used.
These pieces of equipment can be used in a generally called “distributed system”, that is, a system that enables controlling a device that can be controlled via a network from a mobile terminal. The distributed system generally has a configuration in which a controlled device has a state and the state that the controlled device has is changed in response to a message transmitted from the mobile terminal. In addition, in order to prevent a state from being changed unintentionally by a plurality of terminals, the controlled device manages information on a mobile terminal that is a control source, and issues, to the mobile terminal, a control right of the controlled device or a control right waiting report in response to a control right request from the mobile terminal. On the conditions above, a mobile terminal does not need to continuously monitor a device to be controlled, and a network load on the mobile terminal can be reduced. In addition, because it is assumed that there are many mobile terminals and controlled devices in a system, it is unrealistic to have all controlling/controlled relations. Therefore, the respective mobile terminals and controlled devices may have only information on controlled devices that the respective mobile terminals control and information on mobile terminals by which the respective controlled devices are controlled, respectively.
As the distributed system described above, a distributed system is known that enables detecting deadlocks between transactions (global transactions) that are generated so as to stretch over a plurality of resource managers that perform database access or the like (for example, Patent Document 1). In the distributed system above, as an example, a transaction manager that collectively manages transactions may detect deadlocks that are generated between a plurality of transactions so as to stretch over a plurality of resource managers and that result from a wait-for relation relating to occupation of software resources.
A method is also known for detecting deadlocks effectively in a multi-task system in which a plurality of tasks are executed in parallel and which resource each of the tasks occupies is managed (for example, Patent Document 2). In this multi-task system, a wait-for management table is provided so as to register a “wait-for relation” of each of the tasks, and deadlocks can be detected from the wait-for relation.
A distributed system is also known in which deadlocks are detected and eliminated on the basis of individual locks in a process (for example, Patent Document 3). In this system, a distributed transaction manager stores a wait-for graph that includes nodes representing transactions and edges representing dependencies between the transactions, and propagates probes through the wait-for graph so as to detect cyclic dependencies that indicate deadlock dependencies.
As a method for detecting and eliminating deadlocks, a time-out system is known by which an occupation right of a controlled device is forcibly released when a time to wait for the occupation right of the controlled device exceeds a prescribed time period (for example, Patent Document 2). As a deadlock detecting system by which time-out is not performed, a system is known for eliminating deadlocks using a resource circulant graph (for example, Non-Patent Document 1). When deadlock detection is performed using a resource circulant graph, all control relations between terminals and controlled devices need to be stored, and therefore it is difficult to use the resource circulant graph as is, in a distributed system. However, the Chandy-Misra-Haas algorithm is known in which, even when pieces of information are stored while being distributed to terminals and controlled devices, deadlock detection is performed similarly to a resource circulant graph by transmitting messages to destinations that the respective terminals and controlled devices store and by detecting whether the messages returns (for example, Non-Patent Document 2).
[Patent Document 1] Japanese Laid-open Patent Publication No. 8-137707
[Patent Document 2] Japanese Laid-open Patent Publication No. 6-337798
[Patent Document 3] Japanese Laid-open Patent Publication No. 6-214967
[Non-Patent Document 1] R. Holt, “Some dead lock properties of computer systems”, ACM Computing Surveys, vol. 4, pp. 179-196, 1972
[Non-Patent Document 2] K. Chandy, J. Misra, L. Haas, “Distributed deadlock detection”, ACM Trans. Computer Systems, vol. 1, pp. 144-156, 1983
Accordingly, it is an object in one aspect of the embodiments to provide a distributed data processing device, a distributed data processing method, and a distributed data processing program that are capable of detecting deadlocks even when communication between terminals and controlled devices is unavailable.